﻿#include "sort.h"
#include "Stack.h"
void swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

// 插入排序
void InsertSort(int* a, int n)
{
	
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = a[end + 1];

		while (end >= 0)
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
			}
			else
			{
				break;
			}
			end--;
		}
		a[end + 1] = tmp;
	}

}




// 希尔排序
void ShellSort(int* a, int n)
{
	int grp = n;

	while (grp > 1)
	{
		grp = grp / 3 + 1;
		for (int i = 0; i < n - grp; i++)
		{
			int end = i;
			int tmp = a[end + grp];

			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + grp] = a[end];
				}
				else
				{
					break;
				}
				end-=grp;
			}
			a[end + grp] = tmp;
		}
	}

}

//堆排序
void AdjustDwon(int* a, int n, int root)
{
	int father = root;
	int child = father * 2 + 1;
	while (child < n)
	{
		if ((child + 1 < n) && a[child] < a[child + 1])
		{
			child++;
		}
		if (a[father] < a[child])
		{
			swap(&a[father], &a[child]);
		}
		else
		{
			break;
		}
		father = child;
		child = father * 2 + 1;
	}

}
void HeapSort(int* a, int n)
{

	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDwon(a, n, i);
	}
	
	while (n)
	{
		swap(&a[0], &a[n - 1]);
		AdjustDwon(a, n-1, 0);
		n--;
	}
}

// 选择排序
void SelectSort(int* a, int n)
{

	int begin = 0;
	int end = n-1;
	while (begin < end)
	{
		int mini = begin;
		int maxi = begin;
		for (int i = begin; i <= end; i++)
		{
			if (a[i] > a[maxi])
			{
				maxi = i;
			}
			if (a[i] < a[mini])
			{
				mini = i;
			}

		}
		if (maxi == begin)
		{
			maxi = mini;
		}

		swap(&a[mini], &a[begin]);
		swap(&a[maxi], &a[end]);
		begin++;
		end--;
	}

}

// 冒泡排序
void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int exchange = 0;
		for (int j = 0; j < n - 1 - i; j++)
		{
			if (a[j] > a[j + 1])
			{
				swap(&a[j], &a[j + 1]);
				exchange = 1;
			}
		}
		if (exchange == 0)
		{
			break;
		}
	}

}

// 快速排序递归实现
// 快速排序hoare版本
int PartSort1(int* a, int left, int right)
{
	int key = left;
	left++;
	while (left <= right)
	{
		
		while (left <= right && a[left]<a[key])
		{
			left++;
		}
		while (left <= right && a[right] > a[key])
		{
			right--;
		}
		if(left <= right)
		{
			swap(&a[left++], &a[right--]);
		}
	}
	swap(&a[key], &a[right]);
	return right;
}
// 快速排序挖坑法
int PartSort2(int* a, int left, int right)
{
	int hole = left;
	int key = a[left];
	while (left < right)
	{
		while (left < right && a[right] >= key)
		{
			right--;
		}
		a[hole] = a[right];
		hole = right;
		while (left < right && a[left] <= key)
		{
			left++;
		}
		a[hole] = a[left];
		hole = left;
	}
	a[hole] = key;
	return hole;
}
//// 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{
	int key = left;
	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{
		while (a[cur] < a[key] && ++prev != cur)
		{
			swap(&a[prev], &a[cur]);
			
		}
		cur++;
	}
	swap(&a[prev], &a[key]);
	return prev;
}


void QuickSort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	//int key = PartSort1(a, left, right);
	int key = PartSort2(a, left, right);
	//int key = PartSort3(a, left, right);
	QuickSort(a, left, key-1);
	QuickSort(a, key+1, right);
}

// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right)
{
	ST s1;
	STInit(&s1);
	int begin = left;
	int end = right;
	StackPush(&s1, right);
	StackPush(&s1, left);
	while (!StackEmpty(&s1))
	{
		
		begin =  StackTop(&s1);
		StackPop(&s1);
		end = StackTop(&s1);
		StackPop(&s1);

		int key = begin;
		int prev = begin;
		int cur = begin + 1;
		while (cur <= end)
		{
			while (a[cur] < a[key] && ++prev != cur)
			{
				swap(&a[prev], &a[cur]);

			}
			cur++;
		}
		swap(&a[prev], &a[key]);
		key = prev;
		if (begin < prev - 1)
		{
			StackPush(&s1, prev - 1);
			StackPush(&s1, begin);

		}
		if (prev + 1 < end)
		{
			StackPush(&s1, end);
			StackPush(&s1, prev + 1);
		}
	}
	STDestroy(&s1);
}


// 归并排序递归实现

void _MergeSort(int*a , int left,int right,int* tmp)
{
	if (left >= right)
	{
		return;
	}
	int mid = left + (right - left) / 2;
	_MergeSort(a, left, mid, tmp);
	_MergeSort(a, mid+1, right, tmp);

	int begin1 = left;
	int end1 = mid;
	int begin2 = mid+1;
	int end2 = right;
	int index = left;
	while (begin1 <= end1 && begin2 <=end2)
	{
		if (a[begin1] < a[begin2])
		{
			tmp[index++] = a[begin1++];
			
		}
		else
		{
			tmp[index++] = a[begin2++];
		}

	}
	
	
	while (begin1 <= end1)
	{
		tmp[index++] = a[begin1++];

	}
	
	
	while (begin2 <= end2)
	{
		tmp[index++] = a[begin2++];

	}

	
	for (int i = left; i <= right; i++)
	{
		a[i] = tmp[i];

	}
	
	
}


void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	_MergeSort(a, 0, n-1, tmp);
	free(tmp);
}




// 计数排序
void CountSort(int* a, int n)
{
	int max = a[0];
	int min = a[0];
	for (int i = 1; i < n; i++)
	{
		if (a[i] < min)
		{
			min = a[i];
		}
		if (a[i] > max)
		{
			max = a[i];
		}
	}

	int range = max - min + 1;
	int* tmp = (int*)calloc( sizeof(int) , range);
	for (int i = 0; i <n; i++)
	{

		tmp[a[i] - min]++;
	}

	int j = 0;
	for (int i = 0; i < range; i++)
	{
	
		while (tmp[i]--)
		{
			a[j] = i + min;
			j++;
		}

	}
}




/*
非递归排序与递归排序相反，将一个元素与相邻元素构成有序数组，
再与旁边数组构成有序数组，直至整个数组有序。
要有mid指针传入，因为不足一组数据时，重新计算mid划分会有问题
需要指定mid的位置
*/
void merge(int* a, int left, int mid, int right, int* tmp)
{
	// [left, mid]
	// [mid+1, right]
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int index = left;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] <= a[begin2])
			tmp[index++] = a[begin1++];
		else
			tmp[index++] = a[begin2++];
	}

	while (begin1 <= end1)
	{
		tmp[index++] = a[begin1++];
	}

	while (begin2 <= end2)
	{
		tmp[index++] = a[begin2++];
	}

	memcpy(a + left, tmp + left, sizeof(int) * (right - left + 1));
}

/*
k用来表示每次k个元素归并
*/
void mergePass(int* arr, int k, int n, int* temp)
{
	int i = 0;
	//从前往后,将2个长度为k的子序列合并为1个
	while (i < n - 2 * k + 1)
	{
		merge(arr, i, i + k - 1, i + 2 * k - 1, temp);
		i += 2 * k;
	}
	//合并区间[i, n - 1]有序的左半部分[i, i + k - 1]以及不及一个步长的右半部分[i + k, n - 1]
	if (i < n - k)
	{
		merge(arr, i, i + k - 1, n - 1, temp);
	}

}

// 归并排序非递归版
void MergeSortNonR(int* arr, int length)
{
	int k = 1;
	int* temp = (int*)malloc(sizeof(int) * length);
	while (k < length)
	{
		mergePass(arr, k, length, temp);
		k *= 2;
	}
	free(temp);
}
